/*
*
给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：

输入：nums = [1], target = 1
输出：1

提示：

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

  - @author ala
  - @date 2024-09-27 16:05
*/
package main

import "fmt"

func main() {
	nums := []int{1, 1, 1, 1, 1}
	target := 3

	//nums := []int{1, 0}
	//target := 1

	fmt.Println(findTargetSumWays(nums, target))
}

func findTargetSumWays(nums []int, target int) int {
	//return V1(nums, target)
	return V2(nums, target)
}

/**
 *	回溯
 */
func V1(nums []int, target int) int {
	N, res := len(nums), 0
	var bt func(i, crt int)
	bt = func(i, crt int) {
		if i == N {
			if crt == target {
				res++
			}
			return
		}

		bt(i+1, crt+nums[i])
		bt(i+1, crt-nums[i])
	}
	bt(0, 0)
	return res
}

/**
*	背包dp
*	1）假设挑选出的负数和为，p，正数和就是 sum - p
*		target = sum - p - p
*		p = (sum - target) / 2
*		1. sum - target 必须是偶数，否则无解
*		2. sum - target 必须 > 0，否则无解（因为 nums 中没有负数）
*		3. 问题变成，从 nums 中挑一些数出来，总和 = (sum - target) / 2
*	2）dp[i]表示从 nums 中挑一些数，和 = i 的方案数
*		dp[i] = sum(dp[i - nums[j]])
*		dp[0] = 1（什么都不选就能凑出0）
*		dp[target]就是答案
 */
func V2(nums []int, target int) int {
	sum := 0
	for _, n := range nums {
		sum += n
	}
	p := sum - target
	if p < 0 || p&1 == 1 {
		return 0
	}
	p = p >> 1

	//	一维
	dp := make([]int, p+1)
	dp[0] = 1
	for _, n := range nums {
		for i := p; i >= 0; i-- {
			if i-n >= 0 {
				dp[i] += dp[i-n]
			}
		}
	}
	return dp[p]
}
